#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;

class Node{
public:
    Node(string str){
        this->str = str;
    }
public:
    string str;
};


class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>> result;
        for(int i = 0;i<accounts.size();++i){
            for(int j = 1;j<accounts[i].size();++j){
                if(j==1){
                    if(nodes.find(accounts[i][j])==nodes.end()){
                        // name.push_back(accounts[i][0]);
                        nodes[accounts[i][j]] = new Node(accounts[i][j]);
                        parent[nodes[accounts[i][j]]] = nodes[accounts[i][j]];
                    }
                }
                else{
                    if(nodes.find(accounts[i][j])==nodes.end()){
                        // name.push_back(accounts[i][0]);
                        nodes[accounts[i][j]] = new Node(accounts[i][j]);
                        parent[nodes[accounts[i][j]]] = nodes[accounts[i][j]];
                    }
                    UnionSet(accounts[i][j],accounts[i][j-1]);
                }
            }
        }
        while(!nodes.empty()){
            stack<string> nodesDel;
            vector<string> sonResult;
            for(int i = 0;i<accounts.size();++i){
                if(find(accounts[i].begin(),accounts[i].end(),nodes.begin()->first)!=accounts[i].end()){
                    sonResult.push_back(accounts[i][0]);
                    break;
                }
            }
            for(auto i = nodes.begin();i!=nodes.end();++i){
                if(findFather(i->first)==findFather(nodes.begin()->first)){
                    nodesDel.push(i->first);
                    sonResult.push_back(i->first);
                }
            }
            result.push_back(sonResult); 
            //删除nodes中的节点
            while(!nodesDel.empty()){
                nodes.erase(nodesDel.top());
                nodesDel.pop();
            }
        }
        
        return result;


        
    }
    Node* findFather(string str){
        stack<Node*> path;
        Node* node = nodes[str];
        while(parent[node]!=node){
            path.push(node);
            node = parent[node];
        }
        while(!path.empty()){
            parent[path.top()] = node;
            path.pop();
        }
        return node;
    }
    bool isSameSet(string a,string b){
        Node* afather = findFather(a);
        Node* bfather = findFather(b);
        return afather == bfather;
    }
    void UnionSet(string a,string b){
        if(!isSameSet(a,b)){
            Node* afather = findFather(a);
            Node* bfather = findFather(b);
            parent[afather] = bfather;
        }
    }
public:
    // vector<string> name;
    map<Node*,Node*> parent;
    map<string,Node*> nodes;
    
};


int main(){
    Solution S;
    vector<vector<string>> accounts = {{"John", "johnsmith@mail.com", "john00@mail.com"},
                                    {"John", "johnnybravo@mail.com"},{"John", "johnsmith@mail.com", "john_newyork@mail.com"},
                                    {"Mary", "mary@mail.com"}};
    vector<vector<string>> result = S.accountsMerge(accounts);
    return 0;
}